public class BalancedBinaryTree {
    // 自顶向下
    public boolean isBalanced1(TreeNode root) {
        if(root == null) {
            return true;
        }

        // 拿到树的左右子树高度, 相差不超过 1
        int left = treeHeight(root.left);
        int right = treeHeight(root.right);
        // 左右子树执行同样的逻辑
        return Math.abs(left - right) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }

    public int treeHeight(TreeNode root) {
        if(root == null) {
            return 0;
        }

        int left = treeHeight(root.left);
        int right = treeHeight(root.right);
        return Math.max(left, right) + 1;
    }

    // 自底向上
    public boolean isBalanced(TreeNode root) {
        return height(root) != -1;
    }

    public int height(TreeNode root) {
        if(root == null) {
            return 0;
        }

        int left = height(root.left);
        int right = height(root.right);

        if(left == -1 || right == -1 || Math.abs(left - right) > 1) {
            // -1 表示当前树结构是不平衡的
            return -1;
        }else {
            // 返回当前树的最大高度
            return Math.max(left, right) + 1;
        }
    }
}
